class Node:
    def __init__(self, initDate):
        self.date = initDate;
        self.next = None;

    def setDate(self, newDate):
        self.date = newDate

    def setNext(self, newNext):
        self.next = newNext

    def getDate(self):
        return self.date;

    def getNext(self):
        return self.next;


class UnorderedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # 头插法
    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def length(self):
        current = self.head
        count = 0;
        while current != None:
            count += 1
            current = current.getNext()
        return count

    #  尾插法
    def addTail(self, item):
        # temp = Node(item);
        # if self.head==None:
        #     self.head=temp
        # else:
        #     self.tail.next=temp
        # self.tail=temp
        temp = Node(item)  # 新节点
        current = self.head  # 当前节点
        if current is None:
            self.add(item)  # 调用头插入方法
        else:
            while current.getNext() is not None:
                current = current.getNext()  # current下一个节点 以此来推动循环
            current.setNext(temp)  # 尾插入

    # 输出链表
    def date(self):
        currrent = self.head
        lt = []
        while currrent != None:
            lt.append(currrent.getDate())
            currrent = currrent.getNext()
        return lt
    # 查看链表的第k个节点
    def select(self, k):
        current = self.head
        for _ in range(k - 1):
            current = current.getNext()
        return current

    # 在链表已有的一个书之后插入节点
    def insert(self, date, item):
        temp = Node(item)
        current = self.head
        found = False;
        # 找到当前数值所在的节点位置
        while current is not None and not found:
            if current.getDate() == date:
                found = True;
            else:
                current = current.getNext()
        temp.setNext(current.getNext())
        current.setNext(temp)

    # 在链表的第k个结点后插入新结点
    def insertK(self,k,pos,temp):
        if pos=="after":
            current=self.select(k)
            temp.setNext(current.getNext())
            current.setNext(temp)
        elif pos=="before":
            left=self.select(k-1)
            temp.setNext(left.getNext())
            left.setNext(temp)
    # 删除链表的第k个节点
    def removeK(self,k):
        left=self.select(k-1)
        right=left.getNext().getNext()
        left.setNext(right)

    # 反转链表
    def reverse_list(self):
        current = self.head;
        pre = None  # 上个节点
        while current is not None:
            right = current.getNext()  # 用right保存current的下一个节点信息
            current.setNext(pre)  # cureent的下一个节点是他的前一个节点
            # 让 current和pre一次向后以后一个节点，完成循环条件 继续next
            pre = current
            current = right
        self.head = pre


u = UnorderedList()
# 完成单链表的创建
print("完成单链表的创建")
u.add(54)
u.add(26)
u.addTail(93)
u.addTail(17)
u.addTail(77)
u.add(88)
# 打印链表
print("打印链表:",end="")
for i in u.date():
    print(i, end=' ')
print()

# 查看链表的第k个节点
print('查看链表的第{}个节点{}'.format(3, u.select(3).getDate()))

# 在链表的第k个节点插入新节点
print("在链表的第k个节点插入新节点")
temp1=Node(21)
u.insertK(3,"after",temp1)
temp2=Node(75)
u.insertK(3,"before",temp2)

# 打印链表
print("打印链表:",end="")
for i in u.date():
    print(i, end=' ')
print()


# 删除链表的第k个节点
print('删除链表的第{}个节点'.format(4))
u.removeK(4)
print(u.date())


